package com.xzz.poolSampling;

import com.xzz.listnode.ListNode;

import java.util.Random;

/**
 * @author: hhz
 * @create: 2022-01-17 15:02
 * 382. 链表随机节点
 **/
public class ListNodeSolution {

    ListNode head;
    Random random = new Random();
    public ListNodeSolution(ListNode head) {
        this.head = head;
    }
    public int getRandom() {
        int res = head.val;
        int i=0;
        ListNode p = head;
        while (p!=null){
            if(random.nextInt(++i)==0){
                res = p.val;
            }
            p = p.next;
        }
        return res;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(2, new ListNode(3, new ListNode(6, new ListNode(4, new ListNode(9, new ListNode(7, new ListNode(8)))))));
        ListNodeSolution listNodeSolution = new ListNodeSolution(l1);
        System.out.println(listNodeSolution.getRandom());
        System.out.println(listNodeSolution.getRandom());
        System.out.println(listNodeSolution.getRandom());
    }
}
